#include <iostream>
#include <vector>
using namespace std;

// vector<int> computeLPS(string pattern) {
//     int m = pattern.length();
//     vector<int> lps(m, 0);
//     int len = 0;
//     int i = 1;

//     while (i < m) {
//         if (pattern[i] == pattern[len]) {
//             len++;
//             lps[i] = len;
//             i++;
//         } else {
//             if (len != 0) {
//                 len = lps[len - 1];
//             } else {
//                 lps[i] = 0;
//                 i++;
//             }
//         }
//     }

//     return lps;
// }

// vector<int> kmpSearch(string text, string pattern) {
//     vector<int> result;
//     int n = text.length();
//     int m = pattern.length();
//     vector<int> lps = computeLPS(pattern);
//     int i = 0;
//     int j = 0;

//     while (i < n) {
//         if (pattern[j] == text[i]) {
//             j++;
//             i++;
//         }

//         if (j == m) {
//             result.push_back(i - j);
//             j = lps[j - 1];
//         } else if (i < n && pattern[j] != text[i]) {
//             if (j != 0) {
//                 j = lps[j - 1];
//             } else {
//                 i++;
//             }
//         }
//     }

//     return result;
// }

vector<int> computeLPS(string pattern) {
    int n = pattern.size();
    vector<int> lps(n, 0);
    int i = 1; 
    int len = 0;
    while(i < n) {
        if(pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            ++i;
        }else {
            if(len == 0) {
                lps[i] = 0;
                ++i;
            }
            else len = lps[len-1];
        }
    }
    return lps;
}

vector<int> kmpSearch(string pattern, string text) {
    vector<int> result;
    int n = text.size(), m = pattern.size();
    vector<int> lps = computeLPS(pattern);
    int i = 0, j = 0;
    while(i < n) {
        if(text[i] == pattern[j]) {
            ++i; ++j;
        }
        if(j == m) {
            result.push_back(i-j);
            j = lps[j-1];
        }else if(i < n && text[i] != pattern[j]) {
            if(j != 0) j = lps[j-1];
            else {
                ++i;
            }
        }
    }
    return result;
}

// vector<int> computeLPS(string pattern) {
//     int n = pattern.length();
//     vector<int> lps(n, 0);
//     int i = 1, len = 0;
//     while(i < n) {
//         if(pattern[i] == pattern[len]) {
//             ++len;
//             lps[i] = len;
//             ++i;
//         }else {
//             if(len = 0) {
//                 lps[i] = 0;
//                 ++i;
//             }else {
//                 len = lps[len-1];
//             }
//         }
//     }
//     return lps;
// }

vector<int> kmpSearch2(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> lps = computeLPS(pattern);
    vector<int> res;
    int i = 0, j = 0;
    while(i < n) {
        // 先后判断的逻辑不能改变
        if(text[i] == pattern[j]) {
            ++i, ++j;
        }
        if(j == m) {
            res.push_back(i-j);
            j = lps[j-1];
        }
        else if(i < n && text[i] != pattern[j]){
            if(j == 0){
                ++i;
            }else {
                j = lps[j-1];
            }
        }
    }
    return res;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    vector<int> indices = kmpSearch2(text, pattern);

    if (indices.empty()) {
        cout << "Pattern not found in the text." << endl;
    } else {
        cout << "Pattern found at indices: ";
        for (int i = 0; i < indices.size(); i++) {
            cout << indices[i] << " ";
        }
        cout << endl;
    }
    return 0;
}